Markov 链

阐述

离散时间

离散时间 Markov 链是一种随机过程，并且它的概率分布满足

$$\mathbb P(X_i=z_i|X_0,\cdots,X_{i-1})=\mathbb P(X_i=z_i|X_{i-1}=z_{i-1})$$

如果进一步地，这个概率不依赖于 $i$，则它是时间均一的。如无特殊说明，默认它是时间均一的。

转移矩阵表示

对 Markov 链定义 $P^i(x,y)=\mathbb P(X_i=y|X_0=x)$，可以将它看作一个由 $x,y$ 标记的矩阵。这个矩阵的特点是它的每一行之和都为 1。特别地，$P^1=P$ 称为它的转移矩阵。这个矩阵就可以看作是 Markov 链本身。

带权有向图的表示

Markov 链可以用一个带权有向图 $G=(V,E)$ 表示，其中 $V=\mathcal X$，并且如果 $P(x,y)>0$，则 $(x,y)\in E$，并且它的权重就是此概率。此时，该 Markov 链可以看作是一个带权随机游走。

连续时间

第一种定义

若 $N_t$ 是一个 Poisson 过程，$X_i$ 是一个 Markov 链，则 $X_{N_t}$ 是一个 Markov 过程。这个也可以看作：在每一个状态等待一个指数分布的时间，然后跳跃。

定义转移矩阵 $P^t(x,y)=\mathbb P(X_t=t|X_0=x)$，则有

$$P^t(x, y)=\sum_n \frac{(\lambda t)^n}{n !} e^{-t \lambda} K^n(x, y)=\exp(-\lambda t(I-K))$$

第二种定义

生成子：矩阵满足 $Q(x,y)\ge0$ 如果 $x\ne y$，并且它的每行之和为 0。

以 $Q$ 为生成子以及 $\mathcal X$ 为状态空间的随机过程 $X_t$ 定义为：给定 $X_s=x$，等待时间 $\delta t\sim\exp(-Q(x,x))$ 分布的时间，然后按照跃迁矩阵 $K=-D^{-1}(Q-D)$ 选择另一个状态；而如果 $Q(x,x)=0$，则永远停在 $x$。

这个定义也可以解读为：给定 $X_s=x$，对于各个状态 $y$ 我们都有一个独立的 $T_y\sim\exp(Q(x,y))$ 状态，然后移动到使这些 $T_y$ 最小化的状态 $z$。

Markov 性

连续时间的 Markov 性表现为，以 $X_t$ 为条件，未来的 $X_{t+s}$ 与从 $X_t$ 开始的一个 $X_s$ 链的分布是相同的。

实例

赌徒的 Markov 链

令 $\mathcal X=\mathbb N$，$X_i$ 是在时刻 $i$ 拥有的钱，在每一步有 1/2 的几率增加一个或者减少一个。

图上的随机游走

令无向图 $G=(V,E)$，$\mathcal X=V$，每一步 $X_{i+1}$ 从 $X_i$ 的各个邻居中选择。

性质

连通性

给定 Markov 链 $P$ 以及 $x,y\in\mathcal X$，称 $x,y$ 连通（$x\sim y$），如果 $x=y$，或者存在 $i,j>0$ 使得 $P^i(x,y)>0$ 且 $P^j(y,x)>0$。

连通是一种等价关系。这意味着我们可以将 $\mathcal X$ 划分为若干个不相交的等价类，即

$$\mathcal{X}=\mathcal{X}_1 \cup \cdots \cup \mathcal{X}_k$$

连续时间的连通性

对于连续时间 Markov 链，$P^t(x,x)>0$，而 $P^t(x,y)>0$ 当且仅当 $\exists i, K^i(x,y)>0$。

不可约性

这些等价类也称为连通类。在图上，它们相当于图的强连通分量。如果一个 Markov 链只有一个强连通分量，则称它是不可约的。

闭性

一个连通类 $A\subseteq\mathcal X$ 是闭的，如果对于所有的 $x\in A,y\not\in A$，都有 $P(x,y)=0$，也即无法离开 $A$。

对于两个不同的类 $A,B$，我们称 $A\to B$，如果存在 $x\in A,y\in B$ 使得 $P(x,y)>0$。如果 $A\to B$，那么就不能有 $B\to A$。

所有有限状态的 Markov 链都有一个闭类。

周期性

定义 Markov 链 $P$ 的周期为

$$\operatorname{per}(x)=\operatorname{gcd}\left\{i \mid P^i(x, x)>0\right\}$$

同一个连通类中的元素周期总是相同。所以，对于不可约 Markov 链，可以定义它的周期即是任何一个元素的周期。如果周期是 1，那么称它是非周期性的。

对于一个周期 $k$ 的 Markov 链，可以将 $\mathcal X$ 划分为多个不相交的集 $C_1,\cdots,C_k$，其中 $P(x,y)>0$ 当且仅当 $x\in C_i$ 且 $y\in C_{i+1}$。

返回时

给定 $X_0=x$，定义首次返回时

$$\tau_x^+=\min\{i>0|X_i=x\}$$

则 $\tau_x^+$ 也是一个随机变量，它的分布由 $x$ 和 Markov 链 $P$ 决定。

对于不可约 Markov 链以及有限状态空间，总有 $\mathbb E(\tau_x^+)<\infty$。

相关内容

参考文献